package question.interview;

/**
 * https://www.cnblogs.com/cuihongyu3503319/p/10184031.html
 * @Description 字符串相似度算法——Levenshtein Distance算法
 * Levenshtein Distance 算法，又叫 Edit Distance 算法，是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。一般来说，编辑距离越小，两个串的相似度越大。
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.4.27
 */

public class LevenshteinDistance {
    //f(x,y) = min{ f(x-1,y) ,f(x,y-1), f(x-1,y-1) }
    public static void main(String[] args) {
        char[] a = "aaa".toCharArray();
        char[] b = "bbb".toCharArray();
        int[][] ss = new int[b.length][a.length];
        for (int bi = 0; bi < b.length; bi++) {
            for (int ai = 0; ai < a.length; ai++) {
                int tmp = Integer.MAX_VALUE;
                if ( ai == 0 || bi == 0){
                    tmp = 0 ;
                }else{
                    tmp = Math.min(Math.min(ss[bi - 1][ai - 1], ss[bi - 1][ai]), ss[bi][ai - 1]);
                }
                if (b[bi] != a[ai]) {
                    tmp++;
                }
                ss[bi][ai] = tmp;
            }
        }
        System.out.println(ss);
        System.out.println(ss[b.length-1][a.length-1]);
    }
}
